package org.chnxi.study.datastructrues.tree;

/**
 * 线索化二叉树
 * @param <E>
 */
public class ThreadedBinaryTree<E> {

    //记录根节点
    private TBTreeNode<E> root;

    public TBTreeNode<E> getRoot() {
        return root;
    }

    //为了实现线索化，需要创建要给指向当前节点的前驱节点的指针
    //在递归进行线索化时，pre总是保留前一个节点
    private TBTreeNode<E> pre;

    /**
     * 对二叉树进行前序线索化的方法
     * @param node
     */
    public void threadedNodesByPreOrder(TBTreeNode<E> node){
        //空节点不能线索化
        if(node == null){
            return;
        }

        //线索化当前节点
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;

        //线索化左子树
        if(node.getLeftType() == 0){
            threadedNodesByPreOrder(node.getLeft());
        }
        //线索化右子树
        if(node.getRightType() == 0){
            threadedNodesByPreOrder(node.getRight());
        }
    }

    /**
     * 对二叉树进行前序线索化的方法
     */
    public void threadedNodesByPreOrder(){
        threadedNodesByPreOrder(root);
    }

    /**
     * 前序遍历二叉树
     */
    public void printThreadedTreeByPreOrder(){
        TBTreeNode<E> tmp = root;
        while(tmp != null){
            System.out.println("遍历节点："+tmp);

            while(tmp.getLeftType() == 0){
                tmp = tmp.getLeft();
                System.out.println("遍历节点："+tmp);
            }

            while(tmp.getRightType() == 1){
                tmp = tmp.getRight();
                System.out.println("遍历节点："+tmp);
            }

            tmp = tmp.getRight();
        }
    }

    /**
     * 对二叉树进行中序线索化的方法
     * @param node
     */
    public void threadedNodesByInfixOrder(TBTreeNode<E> node){
        //空节点不能线索化
        if(node == null){
            return;
        }

        // 1. 先线索化左子树
        threadedNodesByInfixOrder(node.getLeft());
        // 2. 线索化当前节点
        // 2.1 处理当前节点的前驱节点
        if(node.getLeft() == null){
            //让当前节点的做指针指向前驱节点；
            node.setLeft(pre);
            //表示当前节点的左指针指向的是前驱节点
            node.setLeftType(1);

        }
        // 2.2 处理当前节点的后继节点
        if(pre != null && pre.getRight() == null){
            //让前驱节点的右指针指向当前节点
            pre.setRight(node);
            //让前驱节点的右指针指向的是后继节点
            pre.setRightType(1);
        }
        // 每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;
        // 3. 线索化右子树
        threadedNodesByInfixOrder(node.getRight());
    }

    /**
     * 对二叉树进行中序线索化的方法
     */
    public void threadedNodesByInfixOrder(){
        threadedNodesByInfixOrder(root);
    }

    /**
     * 中序遍历二叉树
     */
    public void printThreadByInfixOrder(){
        TBTreeNode<E> tmp = root;
        while(tmp != null){
            //循环找到LeftType==1的节点，得到的一个节点
            while(tmp.getLeftType() == 0){
                tmp = tmp.getLeft();
            }
            System.out.println("遍历节点："+tmp);
            while(tmp.getRightType() == 1){
                tmp = tmp.getRight();
                System.out.println("遍历节点："+tmp);
            }

            tmp = tmp.getRight();
        }
    }

    /**
     * 对二叉树进行后续线索化的方法
     * @param node
     */
    public void threadedNodesByPostOrder(TBTreeNode<E> node){
        //空节点不能线索化
        if(node == null){
            return;
        }

        // 1. 先线索化左子树
        threadedNodesByPostOrder(node.getLeft());

        // 2. 线索化右子树
        threadedNodesByPostOrder(node.getRight());

        // 3. 线索化当前节点
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;

    }

    /**
     * 对二叉树进行后续线索化的方法
     */
    public void threadedNodesByPostOrder(){
        threadedNodesByPostOrder(root);
    }

    /**
     * TODO 没完成
     */
    public void printThreadedByPostOrder(){
        System.out.println("没实现");
    }


    /**
     * 设置根节点
     *
     * @param node
     */
    public void setRoot(TBTreeNode<E> node) {
        this.root = node;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("TreeNode is Empty !");
        }
    }

    /**
     * 使用前序遍历查找
     * @param e 待查找元素
     * @return
     */
    public TBTreeNode<E> searchByPreOrder(E e){
        if (this.root != null) {
            return this.root.searchByPreOrder(e);
        } else {
            System.out.println("TreeNode is Empty !");
            return null;
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("TreeNode is Empty !");
        }
    }

    /**
     * 使用中序遍历进行查找
     * @param e 待查找元素
     * @return
     */
    public TBTreeNode<E> searchByInfixOrder(E e){
        if (this.root != null) {
            return this.root.searchByInfixOrder(e);
        } else {
            System.out.println("TreeNode is Empty !");
            return null;
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("TreeNode is Empty !");
        }
    }

    /**
     * 使用后序遍历进行查找
     * @param e 待查找元素
     * @return
     */
    public TBTreeNode<E> searchByPostOrder(E e){
        if (this.root != null) {
            return this.root.searchByPostOrder(e);
        } else {
            System.out.println("TreeNode is Empty !");
            return null;
        }
    }

    /**
     * 删除节点
     * @param e 待删除的节点
     * @return
     */
    public boolean delTreeNode(E e){
        boolean result = false;
        //判断树是否为空
        if(root == null){
            return result;
        }

        if(root.getE().equals(e)){  //判断根节点是否为待删除节点
            root = null;
            result = true;
        }else{ //开始判断子树
            result = root.delTreeNode(e);
        }

        return result;
    }
}